package backTrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Class47 {

    List<List<Integer>>  result=new ArrayList<>();
    LinkedList<Integer> path= new LinkedList<Integer>();
    //  CKG TODO 2023/4/22: flag 纵向标记 数组是否使用过
    boolean[] flag;

    public List<List<Integer>> permuteUnique(int[] nums) {
        flag=new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums,flag);
        return result;

    }

    public  void  backTracking(int[] nums,boolean[] flag) {
        if (path.size()== nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        //  CKG TODO 2023/4/22:   cengflag横向标记
//        boolean[]   cengflag=new boolean[nums.length];
//        for (int i = 0; i < nums.length; i++) {
//
//            if (flag[i]==true){
//                continue;
//            }
//            if (i>0&&cengflag[i-1]==true&&nums[i]==nums[i-1]){
//                continue;
////                break;
//            }
//            cengflag[i]=true;
//            flag[i]=true;
//                     path.add(nums[i]);
//            backTracking(nums);
//            flag[i]=false;
//            path.removeLast();
////            cengflag[i]=false;
//        }
        for (int i = 0; i < nums.length; i++) {
            // flag[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
            // flag[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && flag[i - 1] == false) {
                continue;
            }
            //如果同⼀树⽀nums[i]没使⽤过开始处理
            if (flag[i] == false) {
                flag[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
                path.add(nums[i]);
                backTracking(nums, flag);
                path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
                flag[i] = false;//回溯
            }
        }


    }

    public static void main(String[] args) {

        Class47 class47 = new Class47();
        int[] arr={3,0,3,3};
        System.out.println(class47.permuteUnique(arr).toString());

    }


}
